/*
 * @lc app=leetcode.cn id=220 lang=java
 *
 * [220] 存在重复元素 III
 */

// @lc code=start
class Solution {
    //滑动窗口法
    //要求 |i-j| <= k  |nums[i]-nums[j]| <=t，转换问题描述
    //变成某个元素x左侧的k个元素中，如果有某个元素的值落在区间 [x-t,x+t]中即可
    //但是如果用队列，元素无序，那么每个元素都要判断它是否在这个区间，开销大。
    // 由于要使用滑动窗口，所以这个数据结构要满足1. 能添加，删除元素 2.能排序 。
    // 使用TreeSet， 它内部可以自动排序，也比较方便的添加元素

    // 实现方面，我们在有序集合中查找大于等于 x-t的最小的元素y，如果y存在，且y≤x+t我们就找到了一对符合条件的元素。完成检查后，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 k，我们将有序集合中最早被插入的元素删除即可。

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);//主要是为了这个方法，它会取set中大于nums[i]-t的最小值
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {//如果存在这个值，且在区间中。
                return true;
            }
            set.add((long) nums[i]);//将元素加入滑动窗口
            if (i >= k) {
                set.remove((long) nums[i - k]);//窗口元素超过k,可以移除掉最早加入的值，这个值在set中不一定是第一个。
            }
        }
        return false;
    }
}

// @lc code=end

